COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	equiva[w88,jmc]		Equivalence classes as first class objects
C00007 ENDMK
C⊗;
equiva[w88,jmc]		Equivalence classes as first class objects

	In mathematics, two of the main operations for constructing
new sorts of entities from old are cartesian product and forming
the set of equivalence classes under an equivalence relation.  For
example, the rational numbers are usually defined as the equivalence
classes of an equivalence relation on pairs of integers.  Many programming
languages allow cartesian product as a way of forming new
data ``types'', but equivalence classes aren't available in
any that I know of.

	In my opinion, this isn't just because no-one has thought of it.
Indeed the possibility is also mentioned in (McCarthy 1963) which first, I
think, proposed cartesian product.  There is a real difficulty.  Namely,
it isn't hard to implement a standard way of representing elements of
cartesian products as data structures that provides reasonable efficiency
--- at least when cartesian products are not used recursively.  Therefore,
the implementer of the language can provide for them in a straightforward
manner.  Even so, cartesian products are often not treated as first class
objects in that a notation for constants is often not provided.

	Providing for equivalence classes is much harder.  There doesn't
seem to be a standard way of doing it that provides efficiency.  The
obvious way of doing it is to pick a member of each equivalence
class as the representative of the class.  This is often the right
thing to do, but it may depend on some mathematics.  For example, when
we regard the rationals as equivalence classes of pairs of integers,
we normally choose as representative of a class, the member in which
the denominator is positive and the numerator and denominator are
relatively prime, i.e. the fraction is in lowest terms.  However, the
reason for wanting equivalence classes may be that there are few of
them and the memory required to represent a class may be less than that
required to represent a member.

	We also often need to be able to index over the members of an
equivalence class.  There isn't a standard way of doing that either.

The Proposal

	The above difficulties suggest a different way of thinking
about computations with equivalence classes and other data types
defined by operations on sets.  We propose a programming language
for computing with elements of sets.  In this language equivalence
classes are first class objects.  Indexing over sets is also
directly used.  However, we give up the idea of a standard representation
of elements of sets and standard ways of indexing known to the compiler.
Instead the user must supply by separate declarations information
about how these things are to be done.  Of course, the user may have
programs to help him, including AI programs.  Thus we are separating
the description of the algorithm {\it per se} from the description of
the data representation and the basic operations on the data types.

Examples

	We illustrate these concepts with several examples.

1. The 15-puzzle and its extensions.